package com.practice.dataStructure.BloomFliter;

import java.util.BitSet;

/**
 * 布隆过滤器主要是为了解决海量数据的存在性问题。
 * 对于海量数据中判定某个数据是否存在且容忍轻微误差这一场景（比如缓存穿透、海量数据去重）来说，非常适合。
 * 布隆过滤器说某个元素存在，小概率会误判。
 * 布隆过滤器说某个元素不在，那么这个元素一定不在。
 */
public class MyBloomFliter {
    //位数组大小
    private static final int DEFAULT_SIZE = 2<<24;
    //基于此设计哈希函数
    private static final int[] SEEDS = new int[]{3,13,23,34,32,123};
    //位数组
    private BitSet bitSet = new BitSet(DEFAULT_SIZE);
    //哈希函数数组
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    public MyBloomFliter(){
        for(int i=0;i<SEEDS.length;i++){
            func[i] = new SimpleHash(DEFAULT_SIZE,SEEDS[i]);
        }
    }

    public void add(Object value){
        for (SimpleHash simpleHash : func) {
            bitSet.set(simpleHash.hash(value),true);
        }
    }

    public boolean contains(Object value){
        boolean ret = true;
        for (SimpleHash simpleHash : func) {
            ret = ret && bitSet.get(simpleHash.hash(value));
        }
        return ret;
    }

    public static class SimpleHash{
        private int cap;
        private int seed;

        public SimpleHash(int cap,int seed){
            this.cap = cap;
            this.seed = seed;
        }

        //计算哈希值
        public int hash(Object value){
            int h;
            return (value==null)? 0 : Math.abs((cap-1) & seed * ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}
